iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 29
1
Software Development

LeetCode30系列 第 29

[LeetCode30] Day29 - 432. All O`one Data Structure

  • 分享至 

  • xImage
  •  

題目

實現一個資料結構,能支持下面4個操作:
執行每個操作,時間複雜度都要求為 O(1)

  1. Inc(stirng Key)
    如果此key已在資料結構中,則其value加1,反之則插入此key,而value等於1。
  2. Dec(string Key)
    如果此key的value等於1,則從資料結構中刪除,如果大於1,將value減1。
    如果此key不存在於資料結構中,則不會做任何事情。
  3. GetMaxKey()
    回傳value最大的key
    如果沒key在資料結構中,則回傳 ""
  4. GetMinKey()
    回傳value最小的key
    如果沒key在資料結構中,則回傳 ""

Code

class AllOne {
public:
    /** Initialize your data structure here. */
    map<string,int> Data;
    AllOne() {
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    void inc(string key) {
        Data[key]++;
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    void dec(string key) {
        map<string,int>::iterator index = Data.find(key);
        if(index!=Data.end()){
            if(index->second==1){
                Data.erase(key);
            }
            else{
                index->second--;
            }
        }
        
    }
    
    /** Returns one of the keys with maximal value. */
    string getMaxKey() {
        if(Data.size() == 0) return "";
        map<string, int>::iterator Max = Data.begin();
        for(map<string,int>::iterator index = Data.begin(); index != Data.end(); index++){
            if(Max->second < index->second) {
                Max = index;
            }
        }
        return Max->first;
    }
    
    /** Returns one of the keys with Minimal value. */
    string getMinKey() {
        if(Data.size() == 0) return "";
        map<string, int>::iterator Min = Data.begin();
        for(map<string,int>::iterator index = Data.begin(); index != Data.end(); index++){
            if(Min->second > index->second) {
                Min = index;
            }
        }
        return Min->first;
    }
};

https://ithelp.ithome.com.tw/upload/images/20201014/20129147WUPwIzSHoO.png


上一篇
[LeetCode30] Day28 - 65. Valid Number
下一篇
[LeetCode30] Day30 - END
系列文
LeetCode3030
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言